package org.usmile.algorithms.leetcode.simple;

import org.usmile.algorithms.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 653. 两数之和 IV - 输入二叉搜索树
 *
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 * 示例 1：
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 * 示例 2：
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 *
 * 提示:
 *
 * 二叉树的节点个数的范围是  [1, 104].
 * -104 <= Node.val <= 104
 * 题目数据保证，输入的 root 是一棵 有效 的二叉搜索树
 * -105 <= k <= 105
 */
public class _0653 {
}

class _0653_Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        List<Integer> nums = inOrder(root);

        int i = 0;
        int j = nums.size() - 1;
        while (i < j) {
            int sum = nums.get(i) + nums.get(j);
            if (sum == k) {
                return true;
            } else if (sum > k) {
                j--;
            } else {
                i++;
            }
        }

        return false;
    }


    private List<Integer> inOrder(TreeNode root) {
        List<Integer> nums = new ArrayList<>();
        inOrder(root, nums);

        return nums;
    }

    private void inOrder(TreeNode node, List<Integer> nums) {
        if (node == null) {
            return;
        }
        inOrder(node.left, nums);
        nums.add(node.val);
        inOrder(node.right, nums);
    }
}

class _0653_Solution2 {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        Set<Integer> set = new HashSet<>();

        return dfs(root, k, set);
    }

    private boolean dfs(TreeNode root, int target, Set<Integer> set) {
        if (root == null) {
            return false;
        }
        if (set.contains(target - root.val)) {
            return true;
        }
        set.add(root.val);

        return dfs(root.left, target, set) || dfs(root.right, target, set);
    }
}